package com.lhcai.lc.other;

/**
 * @author lhcstart
 * @create 2023-02-26 16:05
 */

/**
 * 最大单词长度乘积
 * 给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，
 * 并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
 */
public class lc318 {
    public static void main(String[] args) {

        maxProduct(new String[]{"abcw", "baz", "foo", "bar", "xtfn", "abcdef"});
    }

    public static int maxProduct(String[] words) {

        int n = words.length;
        int idx = 0;
        int[] makes = new int[n];

        //t为一个字节数，通过<< 左移，将单词中存在的字母标记在t里，记为1
        for (String w : words) {
            int t = 0;
            for (int i = 0; i < w.length(); i++) {
                int k = w.charAt(i) - 'a';
                t |= (1 << k);//标记字母
            }
            makes[idx++] = t;
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if ((makes[i] & makes[j]) == 0) {//没有重复字母
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }
}
